package com.cn.algorithm02.class22;

/***
 * @author: hels
 * @description: 给定一个二维数组，映射成一个表格，找出从左上角到右下角路径最小值，移动时只能向下或者向右。
 * <p>
 * 空间压缩技巧：
 *  如果一个值只依赖它之前的值，那么就可以通过本体类似的空间压缩技巧进行处理。
 **/
public class C01_SumMin {
    //      @param: XL 二维数组x轴长度
//      @param: YL 二维数组y轴长度
    static int row = 4;
    static int col = 5;

    public static void main(String[] args) {
        int[][] arr = new int[][]{{4, 3, 6, 4, 4},
                {1, 3, 3, 5, 3},
                {9, 1, 3, 5, 1},
                {2, 5, 2, 4, 5}};
        printArr(arr);
        System.out.println(process(arr, 0, 0, arr[0][0]));
        System.out.println("===========");

        System.out.println(dpProcess(arr));
        System.out.println(minProcess(arr));

//
//        int[] array = arr[0]; // 此处是地址引用，没有开辟新的内存空间存储数据
//        array[1] = 99;
//        for (int i = 0; i < array.length; i++) {
//            System.out.printf("%d ", array[i]);
//        }
//
//        System.out.println();
//        printArr(arr);

    }

    /**
     * 空间压缩技巧：仅新增一个数组来计算
     * @param: arr 源数组
     * @return
     * @throws
     */
    public static int minProcess(int[][] arr) {
        int[] temp = new int[col];
        temp[0] = arr[0][0];
        for (int i = 1; i < col; i++) {
            temp[i] = temp[i - 1] + arr[0][i];
        }

        for (int i = 1; i < row; i++) {
            temp[0] += arr[i][0];
            for (int j = 1; j < col; j++) {
                temp[j] = Math.min(temp[j - 1], temp[j]) + arr[i][j];
            }
        }
        return temp[col - 1];
    }

    public static int dpProcess(int[][] arr) {
        int[][] dp = new int[row][col];
        dp[0][0] = arr[0][0];
        // 第一行/第一列累加和
        for (int i = 1; i < col; i++) {
            dp[0][i] = dp[0][i - 1] + arr[0][i];
        }
        for (int i = 1; i < row; i++) {
            dp[i][0] = dp[i - 1][0] + arr[i][0];
        }

        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + arr[i][j];
            }
        }
        printArr(dp);
        return dp[row - 1][col - 1];
    }

    /**
     * @param: arr
     * @param: x 移动位置x轴 0开始
     * @param: y 移动位置y轴 0开始
     */
    public static int process(int[][] arr, int x, int y, int result) {
        if (x == row - 1 && y == col - 1) {
            return result;
        }

        if (x >= row || y >= col) {
            return Integer.MAX_VALUE;
        }

        // 横向
        int p2 = Integer.MAX_VALUE;
        if (y + 1 <= col - 1) {
            p2 = process(arr, x, y + 1, result + arr[x][y + 1]);
        }

        // 纵向
        int p1 = Integer.MAX_VALUE;
        if (x + 1 <= row - 1) {
            p1 = process(arr, x + 1, y, result + arr[x + 1][y]);
        }
        return Math.min(p1, p2);
    }

    /**
     * 输出器
     */
    public static void printArr(int[][] arr) {
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                System.out.printf("%d ", arr[i][j]);
            }
            System.out.println();
        }
    }

}
